package graph.unweighted.dfs.biPartitionDetection;

import java.util.ArrayList;
import java.util.Arrays;

import graph.unweighted.CandyGraph;

/**
 * 
 * @Title: CandyBiPartitionDetection.java 
 * @Package graph.dfs.biPartitionDetection 
 * @Description: 使用DFS完成二分图检测：
 *                  记录顶点的颜色，可以被染成蓝色和绿色，没有遍历过的话默认是蓝色
 *                  如果在递归遍历的过程中，发现遍历过的顶点和当前顶点的颜色一样的话，
 *                  就表示不是一个二分图
 * @author CandyWall   
 * @date 2021年1月15日 下午2:41:02 
 * @version V1.0
 */
public class CandyBiPartitionDetection {
    private CandyGraph graph;
    private boolean[] visited;  // 记录顶点是否被遍历过，默认都为false
    private boolean[] isBlue;   // 记录顶点的颜色，可以被染成蓝色和绿色，没有遍历过的话默认是蓝色
    public CandyBiPartitionDetection(CandyGraph graph) {
        this.graph = graph;
        visited = new boolean[graph.getVertex_num()];
        isBlue = new boolean[graph.getVertex_num()];
        for(int i = 0; i < graph.getVertex_num(); i++) {
            visited[i] = false;
            isBlue[i] = true;
        }
    }
    
    /**
     * 获取二分图中的两个部分
     * @return
     */
    public ArrayList<Integer>[] getBiParts() {
        if(!isBiPartitionGraph()) {
            return null;
        }
        ArrayList<Integer>[] biParts = new ArrayList[2];
        biParts[0] = new ArrayList<>();
        biParts[1] = new ArrayList<>();
        for(int i = 0; i < isBlue.length; i++) {
            int j = isBlue[i] == true ? 1 : 0;
            biParts[j].add(i);
        }
        return biParts;
    }
    
    // 判断一个图是不是二分图
    public boolean isBiPartitionGraph() {
        for(int v = 0; v < graph.getVertex_num(); v++) {
            if(!visited[v]) {
                if(!dfs(v, true)) {
                    return false;
                }
            }
        }
        return true;
    }
    
    /**
     * 深度优先遍历：判断一个图是不是二分图
     */
    private boolean dfs(int v, boolean color) {
        visited[v] = true;
        isBlue[v] = color;
        for(int w : graph.adjacentVertexes(v)) {
            if(!visited[w]) {
                if(!dfs(w, !color)) {
                    return false;
                }
            }
            // 如果遍历过了，并且颜色和当前顶点颜色相同，那么就不是一个二分图
            else if(isBlue[w] == isBlue[v]) {
                return false;
            }
        }
        return true;
    }
    
    public static void main(String[] args) {
        CandyGraph graph1 = new CandyGraph("testData/graph/dfs/demo4/graph1.txt");
        CandyBiPartitionDetection biPartitionDetected1 = new CandyBiPartitionDetection(graph1);
        System.out.println("当前图是否是二分图：" + (biPartitionDetected1.isBiPartitionGraph() ? Arrays.toString(biPartitionDetected1.getBiParts()) : "否"));
        CandyGraph graph2 = new CandyGraph("testData/graph/dfs/demo4/graph2.txt");
        CandyBiPartitionDetection biPartitionDetected2 = new CandyBiPartitionDetection(graph2);
        System.out.println("当前图是否是二分图：" + (biPartitionDetected2.isBiPartitionGraph() ? Arrays.toString(biPartitionDetected2.getBiParts()) : "否"));
    }
}
